package com.lili.dt;

/**
 * @Auther: 李 力
 * @Date: 2024/8/9
 * @Description: com.lili.dt
 * @version: 1.0
 */
public class CutRod {

    /*
     * 钢条长度: 0  1  2  3  4  5  6  7
     * 对应价值: 0  1  5  5  6  8  9  17
     * 问:怎么切割出最大价值?
     *
     * */

    //钢条数组:数组索引对应钢条长度，值对应数组的价值
    //n: 要切割的钢条总长度
    public static int cutMaxValue(int[] values, int n) {
        int[][] dp = new int[values.length][n + 1];
        for (int i = 1; i < values.length; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (j >= i) {
                    dp[i][j] = Math.max(dp[i - 1][j], values[i] + dp[i][j - i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[values.length - 1][n];
    }
}
